package middle;
import sword.offer.common.ListNode;

/**
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 * */
public class RotateList {

    /**
     * 旋转链表
     * 1. 找到分割点，即找到哪个结点即将称为head结点，哪个结点即将成为tail结点，可以使用快慢指针
     * 2. 分割成两个链表后，将这两个链表组合在一起。
     * 举例： 1， 2， 3， 4， 5   k = 2
     * 我们可以找到分割点是4
     * 那么将链表分为了两个部分 4 ，5 和 1，2，3
     * 我们将后部分插入到前部分之前。变成了4,5，1，2，3
     * */
    class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            if(head == null){
                return null;
            }
            ListNode fast = head;
            ListNode slow = head;
            int size = 0;
            while(fast != null){
                fast = fast.next;
                size++;
            }

            k %= size;
            if(k == 0){
                return head;
            }
            fast = head;
            while(k != 0){
                fast = fast.next;
                k--;
            }

            if(fast == null){
                return head;
            }

            while (fast.next != null){
                fast = fast.next;
                slow = slow.next;
            }

            // 这个时候slow其实就是分割点，指向的是前部分的tail结点
            ListNode newHead = slow.next;
            slow.next = null;
            fast.next = head;

            return newHead;
        }
    }
}
